const { ListNode, LinkedList } = require('../2. 链表/1. 链表基础/1. 建立线性链表.js')
// 给定一个链表的头节点head，链表中每个节点除了next指针之外，还包含一个随机指针random，该指针可以指向链表中的任何节点或者空节点
// 要求将该链表进行深拷贝，返回复制链表的头节点

// 思路，两次遍历链表，第一次遍历，把map中建立旧节点和新节点的映射
// 第二次遍历，更新新链表中的random指针

function copyRandomList(head) {
    if (!head) {
        return null
    }
    let map = new Map
    let cur = head
    while (cur) {
        map.set(cur, new Node(cur.val, null, null))
        cur = cur.next
    }
    cur = head
    while (cur) {
        if (cur.next) {
            map.get(cur).next = map.get(cur.next)
        }
        if (cur.random) {
            map.get(cur).random = map.get(cur.random)
        }
    }
    return map.get(head)
}

function Node(val, next, random) {
    this.val = val
    this.next = next
    this.random = random
}